1. Technical Field of the Invention
This invention relates to digital parallel processing systems, wherein a plurality of nodes communicate via messages over an interconnection network. In particular, this invention deals with networks including circuit switches which do not store and forward the message within the network. This invention further relates to performance improvement techniques for unbuffered networks comprising self-routing switches which include intelligence for minimizing contention problems.
2. Background Art
In parallel systems, a plurality of nodes communicate via messages sent over an interconnection network. Each node usually interfaces to the network via a network adapter.
For self-routing circuit-switched networks, as described in U.S. Pat. No. 5,654,695, issued Aug. 5, 1997, for "Multi-Function Network", a network adapter sending a message (the sending adapter) searches for a non-blocked alternate path through the network. This search is conducted by trying one alternate path at a time until a successful connection is made across the network to a receiving adapter at another node. An unsuccessful attempt to find a path results in the network returning a rejection signal to the sending adapter to indicate that the attempt has failed. The sending adapter responds by selecting a different alternate path and attempting again to send the message.
The path searching approach for establishing a connection across the network is improved by the dual priority switches in U.S. Pat. No. 5,444,705, "Dual Priority Switching Apparatus for Simplex Networks" by Olnowich et al. The dual priority switch permits the "Multi-Function Network" to make a connection across the network by either path searching or using the camp-on method. The camp-on method uses a high priority path through the network, which proceeds to make connections at each stage of the network until blockage is encountered. Thereupon, the high priority connection command being blocked is stored at the switch stage at the point of blockage and held pending until the blockage ends. Thus, the desired connection to a switch output port that is busy is camped-on until the desired output port becomes available.
Further network performance enhancements featuring non-blocking networks are disclosed in U.S. Pat. No. 5,933,428, issued Aug. 3, 1999, for "TWO-TAILED ADAPTER FOR SCALABLE, NON-BLOCKING NETWORKS" by Olnowich. Non-blocking means that the network will never prevent the connection of two idle nodes attached to the network. That is, when a non-blocking network searches for a path across the network, it will always find at least 1 available path. Thus, the problem of the network preventing a connection from being made is solved.
However, further problems exist which can prevent connections from being successful across the network. The prime problem for a non-blocking network is contention. Contention means that two or more users are competing for the same resource at the same time. In relation to networks, contention means that two or more sending adapters are competing to make a connection to the same receiving adapter on the other side of the network at the same time. In a non-blocking network, any sending adapter will find a path across the network to any receiving adapter; but, if there is contention, even if that path is found across the network, the connection still cannot be made. In a typical example, node 1 is sending a message to node 20, and node 2 also wants to send a message to node 20. Node 2 makes it across the network, but cannot connect because node 20 is busy being connected to node 1.
A good solution for resolving contention, if the message is short, is the camp-on approach discussed-above. This means that the path node 2 found across the network will be held active, and node 2 will wait for node 1 to finish its message. Then node 2 will proceed. However, the use of the camp-on method can defeat the non-blocking characteristic of the network. If two or more paths across the network are being held active waiting to make connection to the same contended destination, a possibility is created in the network where some other sending adapter might no longer be able to find a path across the network to an idle node. This is because more than one path is being dedicated to the node in contention. These periods of possible in the network, will probably go unnoticed if the messages being transferred are short.
However, a problem arises for long messages, such as movie segments or data bases. The camp-on approach then becomes self-defeating in that it solves the contention problem in the best way possible (wait for the contended node to become available), but it creates blocking problems in the network for long periods of time.
Consequently, it as an object of this invention to provide a system which minimizes the losses due to contention in non-blocking networks. It is a further object of the invention to minimize such losses when transmitting long messages.